package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/3/31 14:26
 */
public class C110 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /** 是否平衡二叉树, 左子树,右子树高度差不超过1 */
    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    public static class Info {
        int h;
        boolean isBalanced;

        public Info(int h, boolean isBalanced) {
            this.h = h;
            this.isBalanced = isBalanced;
        }
    }

    public static Info process(TreeNode cur) {
        if(cur == null) {
            return new Info(0, true);
        }
        Info lInfo = process(cur.left);
        Info rInfo = process(cur.right);
        int h = Math.max(lInfo.h, rInfo.h) + 1;
        boolean isBalanced = lInfo.isBalanced && rInfo.isBalanced;
        if(isBalanced && Math.abs(lInfo.h-rInfo.h) > 1) {
            isBalanced = false;
        }
        return new Info(h, isBalanced);
    }

}
